package codeTop;

import java.util.*;

public class q518 {
    //错误
    public int change1(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        Arrays.sort(coins);
        dp[0] = 1;
        for (int i = 1; i <=amount ; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] += dp[i-coins[j]];
                }else {
                    break;
                }
            }
        }
        return dp[amount];
    }

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        for (int i = 0; i < coins.length + 1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < coins.length+1; i++) {
            for (int j = 1; j < amount+1; j++) {
                dp[i][j] = dp[i-1][j]+(j-coins[i-1]>=0?dp[i][j-coins[i-1]]:0);
            }
        }
        return dp[coins.length][amount];
    }
}
